A digital communications system includes an encoder (or transmitter) for encoding and transmitting data, a decoder (or receiver) for receiving and decoding data, and a channel between the encoder and decoder. The channel is generally noisy and causes corruption in the data transmitted therethrough. For the correct data to be recovered, an error-correction code is used during encoding at the encoder side and used by the decoder to correct the corruption in the data. One popular type of such error-correction code is called the Reed-Solomon (RS) code. An encoder/decoder utilizing the RS code is called an RS encoder/decoder. The RS code is briefly explained next.
RS codes are nonbinary codes, i.e., the unit thereof is not a binary bit, but rather a symbol made up of multiple binary bits. For example, in an 8-bit-byte system, each symbol (or byte) contains 8 binary bits and an RS code contains a number of symbols. In the following description, it is assumed that each symbol is composed of m binary bits, where m is an integer. A symbol containing m bits, am−1, am−2, . . . , a0, may be represented by an (m−1)-degree polynomial, K(x)=am−1xm−1+am−2xm−2+ . . . +a0, where x is the indeterminate. Thus, the collection of all 2m possible m-bit symbols constitute a set {K(x)=am−1xm−1+am−2xm−2+ . . . +a0}, where ai ∈{0,1} for i=0, 1, . . . , m−1.
Set {K(x)}, coupled with an addition operator (+) and a multiplication operator (×) defined thereupon, defines a finite field, or Galois field, which may be denoted as GF(2m). Particularly, the addition of the elements of GF(2m) (or elements of {K(x)}) is defined as a binary addition of the corresponding polynomials, where the coefficients of the same powers in the corresponding polynomials are added modulo 2. The modulo-2 addition is defined as a binary addition with no carry, for example, 0+1=1, and 1+1=0. When two elements of GF(2m) are multiplied, the corresponding polynomials are multiplied and reduced to a residue modulo f(x), i.e., multiples of f(x) are reduced to 0. Here f(x) is an m-degree primitive polynomial of GF(2m), which by definition is irreducible and divides xn+1 when n=2m−1, but does not divide xn+1 when n<2m−1. Thus, the addition or multiplication of two elements of GF(2m) generates a polynomial of order not greater than m−1, which corresponds to another element of GF(2m).
It is well known that GF(2m) as defined above includes a so-called primitive element α that is a root of f(x), and every element of GF(2m) except 0 is a power of α. Because f(x) divides x2m−1+1, there is α2m−1=1 (note that this is equivalent to saying α2m−1+1=0 in binary arithmetic). Thus, the elements of GF(2m) are 0, 1(=α0), α1, . . . , α2m−2.
With each element of GF(2m) representing an m-bit symbol, a data sequence containing a sequence of symbols may be represented by a vector including a sequence of elements of GF(2m). For example, a sequence of symbols represented by n (n being an integer) elements of GF(2m), cn−1, cn−2, . . . , c0, form an n-degree vector C over GF(2m), (cn−1, cn−2, . . . , c0. C may be further represented by a polynomial with the sequence of elements of GF(2m) as coefficients of the polynomial, i.e., C(x)=cn−1xn−1+cn−2xn−2+ . . . +c0.
According to the conventional method for RS encoding, redundant symbols are added to a message block to form an RS code, where the redundant symbols and the symbols of the message block satisfy a predetermined condition. The RS code is then transmitted through a channel. A receiver receives the transmitted RS code and determines if the RS code has been corrupted by evaluating whether the received RS code still satisfies the same condition. The receiver corrects any error in the received RS code and extracts the message block therefrom.
Particularly, when a message block M containing k symbols, mk−1, mk−2, . . . , m0, is encoded, a parity sequence P containing a number of redundant symbols (also called parity symbols) is appended to the end of message block M to form an n-degree vector C, where 0<k<n<2m+2. Thus, vector C includes k message symbols of message block M, mk−1, mk−2, . . . , m0, followed by n−k parity symbols, pn−k−1, pn−k−2, . . . , p0, and may be expressed as
                                                                        C                ⁡                                  (                  x                  )                                            =                            ⁢                                                                    m                                          k                      -                      1                                                        ⁢                                      x                                          n                      -                      1                                                                      +                                                      m                                          k                      -                      2                                                        ⁢                                      x                                          n                      -                      2                                                                      +                …                +                                                      m                    0                                    ⁢                                      x                                          n                      -                      k                                                                      +                                                                                                      ⁢                                                                    p                                          n                      -                      k                      -                      1                                                        ⁢                                      x                                          n                      -                      k                      -                      1                                                                      +                                                      p                                          n                      -                      k                      -                      2                                                        ⁢                                      x                                          n                      -                      k                      -                      2                                                                      +                …                +                                  p                  0                                                                                                        =                            ⁢                                                                    x                                          n                      -                      k                                                        ⁢                                      M                    ⁡                                          (                      x                      )                                                                      +                                                      P                    ⁡                                          (                      x                      )                                                        .                                                                                        (        1        )            The encoding is carried out such that C(x) is divisible by a generator polynomial
                                          g            ⁡                          (              x              )                                =                                    ∏                              i                =                1                                            l                +                n                -                k                -                1                                      ⁢                                                  ⁢                          (                              x                -                                  α                  ⅈ                                            )                                      ,                  i          .          e          .                ,                                  ⁢                              g            ⁡                          (              x              )                                ❘                      C            ⁡                          (              x              )                                      ,                            (        2        )            where l is called the offset and may be any integer. In the following, it is assumed that l=1 for simplicity. If C satisfies condition (2), C is called a valid codeword or a codeword. It is well known that an RS code is cyclic, meaning that if an n-symbol sequence C, cn−1, cn−2, . . . , c0, is a valid codeword, then when C is shifted by b symbols to generate a new sequence Cb, cn−b−1, cn−b−2, . . . , c0, cn−1, cn−2, . . . , cn−b, Cb is also a valid codeword, where b is any integer.
After encoding, vector C is transmitted through the channel.
At the decoder side, a vector R corresponding to codeword C is received and includes rn−1, rn−2, . . . , r0, which may differ from the original n symbols of C, mk−1, mk−2, . . . , m0, pn−k−1, pn−k−2, . . . , p0, due to noise in the channel. The decoder then decodes R to recover C as follows.
First, syndromes are computed for R. Syndromes of R are defined as Si=R(αi+1) for i=0, 1, . . . , n−k−1, where R(x) is the polynomial representation of R:R(x)=rn−1xn−1+rn−2xn−2+ . . . +r0.  (3)From (2), if no error occurs in the received vector R, Si should be 0 for i=0, 1, . . . , n−k−1, because g(x)|(R(x)=C(x)). However, if it is assumed there are t errors occurring at unknown locations j1, j2, . . . , jt, and the errors in the received symbols of R at these locations have values e1, e2, . . . , et, where ei=rji−cji, for i=1, 2, . . . , t, then there is:R(x)=C(x)+e(x),  (4)where e(x)=e1xj1+e2xj2+ . . . +etxjt, is the error polynomial. For convenience, error locator numbers β1, β2, . . . , βt, are defined as followsβi=αji, for i=1, 2, . . . , t.  (5)Combining (2), (4), and (5), there are:S0=e1β1+e2β2+ . . . , +etβt,S1=e1β12+e2β22+ . . . +etβt2,. . .Sn−k−1=e1β1n−k+e2β2n−k+ . . . +etβtn−k.  (6)
Because there are 2t unknowns, e1, e2, . . . , et, β1β2, . . . , βt, and (6) has n−k equations, a solution may be found if n−k≧2t. In other words, the RS code can correct up to └(n−k)/2┘ errors, where └x┘ is the floor function which gives the greatest integer not greater than x.
To facilitate solving the equations in (6), an error locator polynomial σ(x) is defined as
                                          σ            ⁡                          (              x              )                                =                                                    ∏                                  i                  =                  1                                t                            ⁢                              (                                  1                  -                                                            β                      i                                        ⁢                    x                                                  )                                      =                                          ∑                                  i                  =                  0                                t                            ⁢                                                σ                  i                                ⁢                                  x                  i                                                                    ,                            (        7        )            an error evaluator polynomial ω(x) is defined as
                                          ω            ⁡                          (              x              )                                =                                                    ∑                                  j                  =                  1                                t                            ⁢                                                e                  j                                ⁢                                  β                  j                                ⁢                                                                            ∏                                              i                        =                        1                                            t                                                              i                      ≠                      j                                                        ⁢                                      (                                          1                      -                                                                        β                          i                                                ⁢                        x                                                              )                                                                        =                                          ∑                                  i                  =                  0                                                  t                  -                  1                                            ⁢                                                ω                  i                                ⁢                                  x                  i                                                                    ,                            (        8        )            and a syndrome polynomial S(x) is defined as
                              S          ⁡                      (            x            )                          =                              ∑                          i              =              0                                      n              -              k              -              1                                ⁢                                    S              i                        ⁢                                          x                i                            .                                                          (        9        )            From (6)-(9), there isS(x)σ(x)=ω(x) mod xn−k.  (10)
Equation (10) is called the key equation, and may be solved by a computer system applying a modified Euclidean (ME) algorithm to find σ(x) and ω(x). After σ(x) and ω(x) are determined, the location of the errors are determined by determining the roots of σ(x), which may be carried out by performing a Chien search. The Chien search simply computes the value of σ(x) at points α0, α−1, . . . , α−(n−1). Note that, because α2m−1=1, evaluating σ(x) at points α0, α−1, . . . , α−(n−1) is equivalent to evaluating σ(x) at points α0=α2m−1, α2m−2, . . . , α2m−n. By definition of σ(x) in (7), if an error occurs at location ji, then σ(βi−1)=σ(α−ji)=0. If σ(α−1)≠0, then no error took place at location i. Also, from (7) and (8), the error values may be computed according to the following expression for a Forney algorithm:
                              e          i                =                  {                                                                                          0                    ,                                                                                                              if                      ⁢                                                                                          ⁢                                              σ                        ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      ≠                    0                                                                                                                                                                  ω                        ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                                                      σ                          ′                                                ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      ,                                                                                                              if                      ⁢                                                                                          ⁢                                              σ                        ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      =                    0                                                                        ,                                              (        11        )            for i=1, 2, . . . , t, where σ′(x) is the derivative of σ(x):
                                          σ            ′                    ⁡                      (            x            )                          =                  -                                    ∑                              j                =                1                            t                        ⁢                                          β                j                            ⁢                                                                    ∏                                          i                      =                      1                                        t                                                        i                    ≠                    j                                                  ⁢                                                      (                                          1                      -                                                                        β                          i                                                ⁢                        x                                                              )                                    .                                                                                        (        12        )            
If l≠1, there is
                              e          i                =                  {                                                                                          0                    ,                                                                                                              if                      ⁢                                                                                          ⁢                                              σ                        ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      ≠                    0                                                                                                                                                                                            -                                                      α                                                          -                                                              i                                ⁡                                                                  (                                                                      l                                    -                                    1                                                                    )                                                                                                                                                                    ⁢                                                  ω                          ⁡                                                      (                                                          α                                                              -                                i                                                                                      )                                                                                                                                                σ                          ′                                                ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      ,                                                                                                              if                      ⁢                                                                                          ⁢                                              σ                        ⁡                                                  (                                                      α                                                          -                              i                                                                                )                                                                                      =                    0                                                                        .                                              (                  11          ⁢                      -                    ⁢          1                )            
The errors are then subtracted from R, i.e., ci=rji−eji, for i=1, 2, . . . , t, to generate the correct codeword C.
In “High-Speed VLSI Architecture for Parallel Reed-Solomon Decoder,” Hanho Lee, IEEE Trans. on Very Large Scale Integration Systems, v. 11, No. 2, April 2003, pp. 288-294 (“Lee”), the entire contents of which are incorporated herein by reference, an RS decoder implementing the above decoding method was proposed. The RS decoder of Lee is briefly discussed herein, with reference to the figures of Lee, which are reproduced here as FIGS. 1, 2A-2B, 3A-3B, and 4A-4C.
FIG. 1 shows a digital communications system including the RS decoder. An encoder encodes k symbols to generate an n-symbol codeword. The n-symbol codeword is transmitted through a channel and is received by the decoder. The decoder includes two parts: an error detection part and an error correction part. In the error detection part, a syndrome computation block computes the n−k syndromes. In the error correction part, a modified Euclidean (ME) algorithm block generates the error-locator polynomial σ(x) and the error-evaluator polynomial ω(x), using the n−k syndromes. The error-locator polynomial σ(x) and the error-evaluator polynomial ω(x) are sent to a Chien search block, which computes σ(x) and σ′(x) at points α0, α1, . . . , αn−1. A Forney algorithm block then computes the error values based on ω(x) and σ′(x). An Error correction block finally corrects the received vector R using the error locations and the error values.
FIGS. 2A-2B, 3A-3B, and 4A-4C show the detailed logic diagrams of the decoder. FIGS. 2A and 2B show the logic diagrams of the syndrome computation block where FIG. 2A shows a syndrome calculation cell and FIG. 2B shows a total of 16 syndrome cells of FIG. 2A connected in series for calculating 16 syndromes (n−k=16). As shown in FIG. 2A, the n symbols of R are input into each syndrome calculation cell for calculating the corresponding syndrome. As shown in FIG. 2B, the 16 syndromes are output serially.
FIGS. 3A and 3B show the logic diagrams of the ME algorithm block, where FIG. 3A shows an ME processing element (PE) and FIG. 3B shows 16 ME PE's, PE1, PE2, . . . , PE16, connected in series for calculating σ(x) and ω(x). The ME algorithm applied in Lee is summarized as follows:                1. First, let R0(x)=xn−k, Q0(x)=S(x), L0(x)=0, U0(x)=1        2. Repeat the calculation of Ri(x), Qi(x), Li(x), Ui(x), i being the index starting from 1, where for each i-th iteration,Ri(x)=[λi−1bi−1Ri−1(x)+ λi−1ai−1Qi−1(x)]−x|li−1|[λi−1ai−1Qi−1(x)+ λi−1bi−1Ri−1(x)],Qi(x)=λi−1Qi−1(x)+ λi−1Ri−1(x),Li(x)=[λi−1bi−1Li−1(x)+ λi−1ai−1Ui−1(x)]−x|li−1|[λi−1ai−1Ui−1(x)+ λi−1bi−1Li−1(x)],Ui(x)=λi−1Ui−1(x)+ λi−1Li−1(x),where ai−1, and bi−1 are the leading coefficients of Ri−1(x) and Q−1(x), respectively, and        
                    l                  i          -          1                    =                        deg          ⁡                      (                                          R                                  i                  -                  1                                            ⁡                              (                x                )                                      )                          -                  deg          ⁡                      (                                          Q                                  i                  -                  1                                            ⁡                              (                x                )                                      )                                ,                  ⁢    and              λ              i        -        1              =          {                                                                  1                ,                                                                                      if                  ⁢                                                                          ⁢                                      l                                          i                      -                      1                                                                      ≥                0                                                                                        0                ,                                                                                      if                  ⁢                                                                          ⁢                                      l                                          i                      -                      1                                                                      <                0                                                    .            The reiteration of step 2 stops when deg(Ri(x))<└(n−k)/2┘;                3. ω(x)=Ri(x), and σ(x)=Li(x).FIG. 3A shows that the ME PE includes two parts, a degree computation (DC) block and a polynomial arithmetic (PA) block. The DC block computes the degrees of Ri(x) and Qi(x) and also calculates λi. The PA block calculates Ri(x), Qi(x), Li(x), Ui(x).        
When σ(x) is determined, the coefficients thereof, σ0, σ1, . . . , σt, are sent to the Chien search block for evaluating σ(x) and σ′(x) for x=α0, α1, . . . , αn−1, as shown in FIG. 4A. Because in binary arithmetic, A(x)+A(x)=0, there is xσ′(x)=σodd(x). Thus, as shown in FIG. 4A, σ′(x) may be calculated at the same time σ(x) is calculated. The Chien search cells, labeled as Ci in FIG. 4A, compute the i-th term in σ(x) or σ′(x), and the result of all the Chien search cells are summed up to generate σ(x) and σ′(x). FIG. 4B shows the detail of the i-th Chien search cell. The Chien search block outputs in series σ(α0), σ(α1), . . . , σ(αn−1).
Similarly, the coefficients of ω(x), ω0, ω1, . . . , ωi−1, are sent to the Forney algorithm block, as shown in FIG. 4C, for the calculation of ω(x) for x=α0, α1, . . . , αn−1. The Forney algorithm block of FIG. 4C also computes the error values according to expression (11), based on the results of σ(x), σ′(x), and ω(x). The error values are then added to the received n symbols of R to generate the correct codeword C.
An RS code that encodes k-symbol message blocks and generates n-symbol codewords, where 0<k<n<2m+2, is referred to as an RS(n, k) code. An RS(n, k) code includes r=n−k parity symbols in each codeword. Generally, n=2m−1. For example, in an 8-bit-symbol system, a standard RS code (also called a mother RS code), RS(255, 239), encodes 239-symbol message blocks into 255-symbol codewords.
In order to offer different coding rates, RS(n, k) codes are frequently modified to generate RS(n′, k′) codes for encoding and decoding k′-symbol message blocks, where n′<n, k′<k, and k′<n′, through shortening and puncturing. FIGS. 5A-5B illustrate the shortening and puncturing of an RS(n, k) code into an RS(n′, k′) code. The shortening of the code is carried out by setting k−k′ symbols (“shortened symbols”) in each codeword to be predetermined symbols, such as 0's. An encoder treats the k′ symbols of a message block and the predetermined k−k′ symbols as a k-symbol message block and generates r parity symbols. The puncturing of the code is then carried out by erasing/puncturing s symbols of the n−k parity symbols, where s=r−r′=(n−k)−(n′−k′). The k−k′ shortened symbols and s punctured parity symbols are not transmitted. Thus, only n′ symbols are transmitted for each codeword, including k′ message symbols and r′ parity symbols.
When a shortened/punctured vector R′ including n′ symbols, rn′−1, rn′−2, . . . , r0, is received, the decoder reconstructs a corresponding n-symbol vector R, by adding the shortened k−k′ symbols and the punctured s parity symbols to the n′ symbols of R′. The values and positions of the shortened symbols are known. The values of the punctured s parity symbols are unknown; however, their positions are predetermined and known to the decoder. The positions of the shortened and erased symbols may be randomly chosen. However, generally the first k−k′ symbols of each codeword are chosen for shortening and the last s parity symbols are chosen for puncturing, as shown in FIGS. 5A and 5B. Also, for convenience and simplicity, the shortened symbols are 0's and the decoder assumes the erased symbols also to be 0's. Thus, the reconstructed vector R includes n symbols, 0, 0 , . . . , 0, rn′−1, rn′−2, . . . , r0, 0, 0, . . . , 0, where there are k−k′ 0's before rn′−1, and s 0's after r0. The decoder then decodes R to find the error/erasure values therein to generate the correct codeword, as discussed below.
When both erasures and errors are present, the decoding process discussed above must also address the erasures. First, when R is reconstructed, syndromes may be calculated using the syndrome computation block of FIGS. 2A-2B: Si=Rs(αi+1) for i=0, 1, . . . , n−k−1, where R(x)=rn′−1xs+n′−1+rn′−2xs+n′−2+ . . . +r0xs. Assuming vector R includes t errors at positions j1, j2, . . . , jt, and s erasures at positions jt+1, jt+2, . . . , jt+s, and the error/erasure values e1, e2, . . . , et+s then e(x)=e1xj1+e2xj2+ . . . +et+sxjt+s is the error/erasure polynomial, where ei=rji−cji, for i=1, 2, . . . , t, and, ei=cji, for i=t+1t+2, . . . , t+s. Let βi=αji, for i=1, 2, . . . , t+s, thenS0=e1β1+e2β2+ . . . +et+sβt+s,S1=e1β12+e2β22+ . . . +et+sβt+s2,. . .Sn−k−1=e1β1n−k+e2β2n−k+ . . . +et+sβt+sn−k.  (13)Because the locations of the erasures are known, βt−1, βt−s, . . . , βt−s are known parameters and may be computed before the decoding process starts. Particularly, in the example above, the last r−r′ parity symbols are erased; therefore, jt+1=r−r′−1, jt+2=r−r′−2, . . . , jt+s, and s=r−r′. There are n−k equations in (13) containing 2t+s unknowns. Thus, equations (13) have a solution if n−k≧2t+s. In other words, an RS(n′, k′) code is capable of correcting t errors and s erasures, provided that n−k≧2t+s.
The error/erasure locator polynomial σ(x) is defined as
                                          σ            ⁡                          (              x              )                                =                                    σ              0                        =                                                            (                  x                  )                                ⁢                                                      σ                    1                                    ⁡                                      (                    x                    )                                                              =                                                ∑                                      i                    =                    0                                                        t                    +                    s                                                  ⁢                                                      σ                    i                                    ⁢                                      x                    i                                                                                      ,                            (        14        )            where
            σ      0        ⁡          (      x      )        =            ∏              i        =                  t          +          1                            t        +        s              ⁢                  ⁢          (              1        -                              β            i                    ⁢          x                    )      is the erasure locator polynomial, which may be computed before the decoding process, and
            σ      1        ⁡          (      x      )        =            ∏              i        =        1            t        ⁢                  ⁢          (              1        -                              β            i                    ⁢          x                    )      is the error locator polynomial. The error/erasure evaluator polynomial ω(x) is defined as
                              ω          ⁡                      (            x            )                          =                                            ∑                              j                =                1                                            t                +                s                                      ⁢                                          e                j                            ⁢                              β                j                            ⁢                                                                    ∏                                          i                      =                      1                                                              t                      +                      s                                                                            i                    ≠                    j                                                  ⁢                                                                  ⁢                                  (                                                                                    β                        i                                            ⁢                      x                                        -                    1                                    )                                                              =                                    ∑                              i                =                0                                            t                +                s                -                1                                      ⁢                                          ω                i                            ⁢                                                x                  i                                .                                                                        (        15        )            From (9) and (13)-(15), there isS(x)σ(x)=ω(x) mod xn−k,  (16)orS(x)σ0(x)σ1(x)=ω(x) mod xn−k.  (17)A modified syndrome polynomial S0(x) may be defined as:S0(x)=S(x)σ0(x).  (18)After the syndromes Si are calculated, the modified syndrome polynomial S0(x) may be calculated according to Expression (18). The key equation is modified as follows:S0(x)σ1(x)=ω(x) mod xn−k.  (19)
The modified key equation may then be solve according to the ME algorithm using the ME algorithm block of FIGS. 3A and 3B, generating the error locator polynomial σ1(x) and error/erasure evaluator polynomial ω(x). Then, the error/erasure locator polynomial σ(x) is calculated according to equation (14), and a Chien search and Forney algorithm (expression (11) above) are performed to find the locations of the errors and the values of the errors and erasures, which are used to recover the correct codeword.
TABLE 1Rate IDModulationRS(n′, k′)0QPSK(32, 24)1QPSK(40, 36)216QAM(64, 48)316QAM(80, 72)464QAM(108, 96) 564QAM(120, 108)
The IEEE 802.16a standard provides six standard shortened/punctured RS codes of a mother code RS(255, 239), as shown in Table 1. The first column, Rate ID, is for identification purposes. The second column shows the modulation schemes, where QPSK stands for quadrature phase shift keying, and QAM stands for quadrature amplitude modulation. The third column shows the resultant RS(n′, k′) codes.